package com.linyaonan.leetcode.medium._240;

import javax.validation.constraints.Max;

/**
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 *
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 *
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
 * 输出：true
 *
 * @author: Lin
 * @date: 2024/9/24
 */
public class SearchA2dMatrixII {

    /**
     * 从题目描述来看矩阵满足横向增长，纵向增长的
     * 可以很自然的想到使用二分查找
     * 1. 首先在第一行找到如果比目标值大，则说明这一列以后右边所有列的数值都会比目标值大，目标值只有可能在该列的前面所有列中
     * 2. 延伸一下，index=m，n这个坐标中，如果比目标值大，则说明目标只能在0-m，0-n这个坐标系中；同理如果比目标值下，那么只能在m-max，n-max这个坐标系
     *
     * 四次比较框出一个范围区间
     * 1. m=0，如果m,n坐标数值大于目标值，则表示从该位置开始向右下的所有数值都会大于目标值直接废弃n(max)=n-1
     * 2. n=0，如果m,n坐标大于目标值，则表示从该位置右下所有数值都会大于目标值进行废弃m(max)=m-1
     * 3. m=max, 如果m,n坐标值小于目标值，则表示从该位置向左上所有数值都会小于目标值直接废弃n(min)=n+1
     * 4. n=max，如果m,n坐标值小于目标值，则表示从该位置左上所有数值都会小于目标值直接废弃m(min)=m+1
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // 1. 异常边界
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        // 2. 单值矩阵
        if (matrix.length == 1 && matrix[0].length == 1) {
            return matrix[0][0] == target;
        }
        // 3. 正常进行二分
        int _nmax;
        int _mmax;
        int _nmin;
        int _mmin;

        // 找到n的右边界
        {
            int nmax = matrix[0].length - 1;
            int nl = 0;
            while (nl < nmax) {
                int tmp = (nl + nmax) >>> 1;
                if (matrix[0][tmp] > target) {
                    nmax = tmp - 1;
                } else {
                    nl = tmp + 1;
                }
            }
            _nmax = nmax;
        }

        // 找到m的右边界
        {
            int mmax = matrix.length - 1;
            int ml = 0;
            while (ml < mmax) {
                int tmp = (ml + mmax) >>> 1;
                if (matrix[tmp][0] > target) {
                    mmax = tmp - 1;
                } else {
                    ml = tmp + 1;
                }
            }
            _mmax = mmax;
        }

        // 找到n的左边界
        {
            int nmin = 0;
            int nr = _nmax;
            while (nmin < nr) {
                int tmp = (nmin + nr) >>> 1;
                if (matrix[matrix.length - 1][tmp] < target) {
                    nmin = tmp + 1;
                } else {
                    nr = tmp - 1;
                }
            }
            _nmin = nmin;
        }

        // 找到m的左边界
        {
            int mmin = 0;
            int mr = _mmax;
            while (mmin < mr) {
                int tmp = (mmin + mr) >>> 1;
                if (matrix[tmp][matrix[0].length - 1] < target) {
                    mmin = tmp + 1;
                } else {
                    mr = tmp - 1;
                }
            }
            _mmin = mmin;
        }


        for (int i = _mmin; i <= _mmax; i++) {
            if (checkHasT(matrix[i], _nmin, _nmax, target)) {
                return true;
            }
        }

        return false;

    }

    private boolean checkHasT(int[] org,int s, int e, int t) {
        while (s <= e) {
            int m = (s + e) >>> 1;
            int _t = org[m];
            if (_t == t) {
                return true;
            } else if (_t < t) {
                s = m + 1;
            } else {
                e = m - 1;
            }
        }
        return false;
    }



}
